Problem statement: zenit16cke

Fuška pre troch

Počet bodov: 30, časový limit: 2000ms

Dezider, Oľga a Gustáv radi lúštia krížovky a hlavolamy všetkého druhu. Miestny mesačník Zenit sa im ozval, či by nevymysleli osemsmerovku do najnovšieho vydania. Celé vydanie sa má venovať prominentnej výstave psov. Redaktor našej trojici preto povedal, že celá osemsmeroka sa má skladať len z písmen D, O a G. Aby sa mohol na obálke pýšiť počtom psov v Zenite, tak rovno chce vedieť, koľko DOG-ov sa v krížovke nachádza.

Aby mesačníku neurobili hanbu, rozhodli sa vyrobiť tú najlepšiu krížovku na svete. Dezider sa krvopotne snažil, celú noc nespal. Na druhý deň ráno s krvou podliatymi očami a víťazoslávnym úsmevom na tvári ukázal zvyšným dvom plody svojej práce. Oľga osemsmerovku ihneď schmatla a začala riešiť. Riešila dva dni a dve noci, no nakoniec osemsmerovku vyriešila.

Keď sa k osemsmerovke konečne dostal Gustáv, hneď začal kritizovať: “Počuj Dezider, tuto roh vyzerá trochu divne, neskúsil by si toto písmeno zmeniť? A toto sem nemôžeme dať, veď to vyzerá ako…”, umlčali ho však pohľady Dezidera a Oľgy. Obrátil sa teda na vás.

Úloha

Máte zadanú osemsmerovku skladajúcu sa z písmen D, O, G a zoznam Gustávových zmien. Každá Gustávova zmena pozostáva zo zmenenia jedného políčka osemsmerovky, pričom máte zadané súradnice políčka aj písmeno, na ktoré sa má meniť.

Pri zmene osemsmerovky zostávajú všetky predchádzajúce zmeny v platnosti.

Vašou úlohou je nájsť počet výskytov reťazca DOG v pôvodnej osemsmerovke, ako aj po každej zmene osemsmerovky.

Vstup a výstup

Na prvom riadku sú čísla \(1 \leq r, c \leq 1000\): počet riadkov a počet stĺpcov osemsmerovky.

Na nasledujúcich \(r\) riadkch je pôvodná osemsmerovka.

Na ďalšom riadku je číslo \(1 \leq n \leq 10\,000\): počet zmien v osemsmerovke.

Nakoniec sa na vsupe nachádza \(n\) riadkov, na ktorých sú medzerami oddelené čísla \(r_i\), \(c_i\) a písmeno \(p_i\): súradnice zmeneného políčka a samotné písmeno. Platí \(1 \leq r_i \leq r\) a \(1 \leq c_i \leq c\).

 Príklad

Input:

3 4
DOGG
ODOG
GODD
3
2 2 O
3 1 D
1 1 D

Output:

5
4
3
3

Všimnite si, že tretia zmena mení písmeno D na písmeno D. Výsledná osemsmerovka bude vyzerať nasledovne:

DOGG
OOOG
DODD